package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 94. 二叉树的中序遍历
 * 模拟系统栈
 *
 * @author fy
 * @date 2022/4/14 8:39
 */
public class Solution94_3 {

    class Command {
        String s;
        TreeNode node;

        Command(String s, TreeNode node) {
            this.s = s;
            this.node = node;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<Command> stack = new LinkedList<>();
        if (root != null) {
            stack.push(new Command("go", root));
        }
        while (!stack.isEmpty()) {
            Command cmd = stack.pop();
            if ("print".equals(cmd.s)) {
                res.add(cmd.node.val);
            } else if ("go".equals(cmd.s)) {
                TreeNode newNode = cmd.node;
                if (newNode.right != null) {
                    stack.push(new Command("go", newNode.right));
                }
                stack.push(new Command("print", newNode));
                if (newNode.left != null) {
                    stack.push(new Command("go", newNode.left));
                }
            }
        }
        return res;
    }

}
